package com.singzi.leetcode.N900;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class T0851 {
    public static void main(String[] args) {
        int [][]richer = {
                {1,0},
                {2,1},
                {3,1},
                {3,7},
                {4,3},
                {5,3},
                {6,3}};
        int [] quiet = {3, 2, 5, 4, 6, 1, 7, 0};

        Solution0851 solution0851 = new Solution0851();
        System.out.println(Arrays.toString(solution0851.loudAndRich(richer, quiet)));

    }
}

class Solution0851 {
    public int[] loudAndRich(int[][] richer, int[] quiet) {

        int length = quiet.length;
        int [][] graph = new int[length][length];
        for (int[] ints : richer) {
            graph[ints[0]][ints[1]] = 1;
        }
        int []result = new int[quiet.length];
        for (int i = 0; i < result.length; i++) {
            result[i] = i;
        }
        for (int i = 0; i < quiet.length; i++) {
            result[i] = bfs1(graph, i, quiet);
        }

//        System.out.println(Arrays.deepToString(graph));
        return result;

    }
    public int bfs1(int [][] graph, int index, int[] quiet){
        int min = quiet[index];
        int minIndex = index;

        Queue<Integer> queue = new LinkedList<>();
        queue.add(index);
        while (!queue.isEmpty()){
            index = queue.remove();
            if(quiet[index] < min) {
                min = quiet[index];
                minIndex = index;
            }
            for (int i = 0; i < graph.length; i++) {
                if(graph[i][index]==1){
                    queue.add(i);
                }
            }
        }


        return minIndex;
    }
    public int bfs(int [][] graph, int index, int[] quiet, int[]result) {

        int min;
        int length = graph.length;
        for (int i = 0; i < length; i++) {
            min = quiet[i];
            for (int j = 0; j < length; j++) {
                if(graph[j][i] != 0){
                    break;
                }
                result[j] = j;
            }

        }

        return 0;


    }
}